package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @description: leetcode 104 二叉树的最大深度
 * @author 勾新杰
 * @version 1.0
 * @date 2025/1/9 12:04
 */
public class E104 {

    /**
     * <h3>方法一：递归求解</h3>
     * @param root 二叉树的根节点
     * @return 二叉树的最大深度
     */
    public int maxDepth1(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth1(root.left) + 1, maxDepth1(root.right) + 1);
    }

    /**
     * <h3>方法二：层序遍历求解</h3>
     * @param root 二叉树的根节点
     * @return 返回二叉树的最大深度
     */
    @SuppressWarnings("all")
    public int maxDepth2(TreeNode root) {
        int level = 0;
        if (root == null) return level;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
            level++;
        }
        return level;
    }

    /**
     * <h3>方法三：迭代求解</h3>
     * @param root 二叉树的根节点
     * @return 二叉树的最大深度
     */
    public int maxDepth3(TreeNode root) {
        int maxDepth = 0;
        if (root == null) return maxDepth;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root, lastPop = null;
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                curr = curr.left;
            }else {
                TreeNode last = stack.peek();
                if (last.right == null){
                    // 左子树为null并且右子树也为null说明这个分叉到底了
                    maxDepth = Math.max(maxDepth, stack.size());
                    lastPop = stack.pop();
                } else if (last.right == lastPop) {
                    lastPop = stack.pop();
                } else {
                    curr = last.right;
                }
            }
        }
        return maxDepth;
    }
}
